package TopKFrequentElements;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;

public class Solution {
    public List<Integer> topKFrequent(int[] nums, int k) {
        HashMap<Integer, Integer> map=new HashMap<Integer, Integer>();
        List<Integer> result=new ArrayList<Integer>();
        int max=0;
        for (Integer t:nums){
        	if (map.get(t)==null)
        		map.put(t, 1);
        	else
        		map.put(t, map.get(t)+1);
        	max=Math.max(max, map.get(t));
        }
        int top=Integer.toString(max).length()-1;
        int mod=1;
        for (int i=1;i<=top;i++)
        	mod=mod*10;
        while (result.size()!=k){
           int[][] bark=new int[10][100];
           Iterator iter=map.keySet().iterator();
           while (iter.hasNext()){
        	   int key=(int) iter.next();
        	   int value=map.get(key);
        	   bark[value%(mod*10)/mod][0]++;
        	   bark[value%(mod*10)/mod][bark[value%(mod*10)/mod][0]]=key;
           }
           for (int i=9;i>=0;i--)
        	   if (k-result.size()>=bark[i][0])
        		   for (int j=1;j<=bark[i][0];j++)
        			   result.add(bark[i][j]);
        	   else{
        		   HashMap<Integer, Integer> nextMap=new HashMap<Integer, Integer>();
        		   for (int j=1;j<=bark[i][0];j++)
        			   nextMap.put(bark[i][j],map.get(bark[i][j]));
        		   map=nextMap;
        		   mod=mod/10;
        		   break;
        	   } 
        }
        return result;
    }
    public static void main(String args[]) {
    	Solution so=new Solution();
    	int[] t={5,1,-1,-8,-7,8,-5,0,1,10,8,0,-4,3,-1,-1,4,-5,4,-3,0,2,2,2,4,-2,-4,8,-7,-7,2,-8,0,-8,10,8,-8,-2,-9,4,-7,6,6,-1,4,2,8,-3,5,-9,-3,6,-8,-5,5,10,2,-5,-1,-5,1,-3,7,0,8,-2,-3,-1,-5,4,7,-9,0,2,10,4,4,-4,-1,-1,6,-8,-9,-1,9,-9,3,5,1,6,-1,-2,4,2,4,-6,4,4,5,-5,
    			7};
    	so.topKFrequent(t, 2);
		
	}
}
